flexibl constrain spectral cluster xiang wang ian davidson constrain cluster studi algorithm mean hierarch agglom cluster encod constraint spectral cluster remain develop area paper propos flexibl gener framework constrain spectral cluster contrast previou effort implicitli encod link link constraint modifi graph laplacian result eigenspac present natur principl formul preserv origin graph laplacian explicitli encod constraint method offer practic advantag encod degre belief weight link link constraint guarante lower bound constraint satisfi user threshold solv determinist polynomi time gener eigendecomposit inherit object function spectral cluster explicitli encod constraint exist analysi spectral cluster techniqu valid work pose natur extens unconstrain spectral cluster interpret find normal min cut label graph valid effect approach empir result real world data set applic constrain imag segment cluster benchmark data set binari degre belief constraint 